package Leetcode.ArrayAndLinkedList.climbStairs70;

/**
 * 用斐波拉契公式计算
 * 1,1,2,3,5,8,13……，
 * 但我们这道题的前几项是1,2,3,5,8……明显比那公式少了一项，所以这里计算第n项的指数应该是n+1
 */
public class Solution2 {
    public static int climbStairs(int n) {
        double sqrt = Math.sqrt(5);
        return (int) ((Math.pow((1 + sqrt) / 2, n + 1) - Math.pow((1 - sqrt) / 2, n + 1)) / sqrt);
    }
}